package leetcode.interviewClassics;

import leetcode.ListNode;

import java.util.List;

/**
 * @author Cheng Jun Description: 给你一个链表的头节点 head 和一个特定值 x ，请你对链表进行分隔，使得所有 小于 x 的节点都出现在 大于或等于 x
 *     的节点之前。
 *     <p>你不需要保留每个分区中各节点的初始相对位置。
 *     <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/partition-list-lcci
 *     著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 * @version 1.0
 * @date 2021/11/1 17:32
 * @see leetcode.listnode.partition 进阶版
 */
public class partition {

  public static void main(String[] args) {
    ListNode listNode5 = new ListNode(2, null);
    ListNode listNode4 = new ListNode(5, listNode5);
    ListNode listNode3 = new ListNode(2, listNode4);
    ListNode listNode2 = new ListNode(3, listNode3);
    ListNode listNode1 = new ListNode(4, listNode2);
    ListNode listNode0 = new ListNode(1, listNode1);
    partition(listNode0, 3);
  }

  // 当前节点 的next的val 值 小于x，就把当前节点的next放到链头， cur.next = cur.next.next
  static ListNode partition(ListNode head, int x) {
    if (head == null) {
      return head;
    }
    ListNode top = head;
    ListNode cur = head;
    while (cur.next != null) {
      if (cur.next.val < x) {
        ListNode temp = cur.next;
        cur.next = cur.next.next;
        // cur.next 放到最前面，并将 top 重新指向最前面
        temp.next = top;
        top = temp;
      } else {
        cur = cur.next;
      }
    }
    return top;
  }

  static ListNode partition1(ListNode head, int x) {
    ListNode small = new ListNode(0);
    ListNode smallHead = small;
    ListNode large = new ListNode(0);
    ListNode largeHead = large;
    while (head != null) {
      if (head.val < x) {
        small.next = head;
        small = small.next;
      } else {
        large.next = head;
        large = large.next;
      }
      head = head.next;
    }
    large.next = null;
    small.next = largeHead.next;
    return smallHead.next;
  }
}
